package com.love.dynamicPlan;


/**
 *
 70. 爬楼梯
 简单
 相关标签
 相关企业
 提示
 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

 示例 1：

 输入：n = 2
 输出：2
 解释：有两种方法可以爬到楼顶。
 1. 1 阶 + 1 阶
 2. 2 阶
 示例 2：

 输入：n = 3
 输出：3
 解释：有三种方法可以爬到楼顶。
 1. 1 阶 + 1 阶 + 1 阶
 2. 1 阶 + 2 阶
 3. 2 阶 + 1 阶
 */
public class StairWalk {


    /**
     * f(x)f(x)f(x) 表示爬到第 xxx 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
     *
     * f(x)=f(x−1)+f(x−2)  这个等式极为关键
     *
     * @param K
     * @return
     */
    public static int up(int K){
        if(K == 1){
            return 1;
        }
        if(K == 2){
            return 2;
        }
        return up(K - 1) + up(K - 2);
    }



    /***************************************************************************/
    public static int up1(int N){

        /**
         * dp[i] : 表示，爬了i层楼梯有多少种走法
         */
        int[] dp = new int[N + 1];

        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= N ; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[N];

    }





    public static void main(String[] args) {
        System.out.println(up(45));
        System.out.println(up1(45));
    }

}
